package fun.coding.jeffreys.judge;


public class FlattenMultiLevelLinkedList {

	public static void main(String[] args) {
		ListNodeWithChild n1 = new ListNodeWithChild(1);
		ListNodeWithChild n2 = new ListNodeWithChild(2);
		ListNodeWithChild n3 = new ListNodeWithChild(3);
		ListNodeWithChild n4 = new ListNodeWithChild(4);
		ListNodeWithChild n5 = new ListNodeWithChild(5);
		ListNodeWithChild n6 = new ListNodeWithChild(6);
		ListNodeWithChild n7 = new ListNodeWithChild(7);
		ListNodeWithChild n8 = new ListNodeWithChild(8);
		ListNodeWithChild n9 = new ListNodeWithChild(9);
		
		n1.next = n2;
		n2.next = n3;
		n3.next = n4;
		n4.next = n5;
		n2.child = n6;
		n6.next = n7;
		n7.child = n8;
		n4.child = n9;
		
		FlattenMultiLevelLinkedList ins = new FlattenMultiLevelLinkedList();
		ListNodeWithChild head = ins.flattenMultiLevelListByLevel(n1);
		
		FlattenMultiLevelLinkedList.printListNodeWithChild(head);
	}

	/**
	 * 1 ->  2 -> 3 ->   4 -> 5
	 *       |           |
	 *       V           V
	 *       6 -> 7      9
	 *            |
	 *            V
	 *            8 
	 *  1, 2, 3, 4, 5, 6, 7, 9, 8
	 *            
	 */
	public ListNodeWithChild flattenMultiLevelListByLevel(ListNodeWithChild head) {
		ListNodeWithChild dummy = new ListNodeWithChild(-1);
		dummy.next = head;
		
		ListNodeWithChild cur = head;
		ListNodeWithChild tail = this.findTail(head);
		
		while (cur != null) {
			if (cur.child != null) {
				tail.next = cur.child;
				cur.child = null;
				tail = this.findTail(tail);
			}
			cur = cur.next;
		}
		return dummy.next;
	}
	
	private ListNodeWithChild findTail(ListNodeWithChild head) {
		ListNodeWithChild tail = head;
		
		while (tail != null && tail.next != null) {
			tail = tail.next;
		}
		return tail;
	}
	
	public static void printListNodeWithChild(ListNodeWithChild head) {
		ListNodeWithChild iter = head;
		
		while (iter != null) {
			System.out.print(iter.val + ",");
			iter = iter.next;
		}
		System.out.println();
	}

}
